package algorithm.leetcode.I1to100;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Q20 {

    public boolean isValid(String s) {
        if (s.equals("")) return true;

        String[] splitted = s.split("");

        Stack<String> tempStack = new Stack<>();
        Map<String, String> map = new HashMap<String, String>() {{
            put("{", "}");
            put("[", "]");
            put("(", ")");
        }};

        for (int i = 0; i < splitted.length; i++) {
            // 如果是左括号,就压栈
            if (map.containsKey(splitted[i])) tempStack.push(splitted[i]);
            // 如果是右括号,看下是否与栈顶的元素匹配,若是,弹栈一个元素,若否,直接返回false
            else {
                if (!tempStack.isEmpty() && map.get(tempStack.peek()).equals(splitted[i])) tempStack.pop();
                else return false;
            }
        }
        return tempStack.isEmpty();
    }

    public static void main(String[] args) {
        Q20 q20 = new Q20();
        q20.isValid("()");
    }
}
